﻿#include "QuadTree.h"


const float offset = 1.15f;
const float maxextra = -1.f;

//check if rect1 is inside rect2
bool inside(const RECT &rect1,const RECT &rect2)
{
	if ((rect1.top >= rect2.top) && (rect1.left >= rect2.left) && (rect1.right <= rect2.right) && (rect1.bottom <= rect2.bottom))
		return true;
	else return false;
}

int QuadNode::CheckRect(RECT rect)
{
	
	RECT childRect;
	int k=0;
	for (int i=1;i<=4;i++)
	{
		childRect = calChildRect(i);
		if (inside(rect,childRect))
			return i;
	}
	
	return k;
}

QuadNode::QuadNode(float x,float y, int width, int height)
{
	_nodeRect = RECT();
	_nodeRect.left = x;
	_nodeRect.right = x + width;
	_nodeRect.top = y;
	_nodeRect.bottom = y + height;

	float newW = width * offset;
	float newH = height * offset;

	float centerX = _nodeRect.left + width / 2;
	float centerY = _nodeRect.top + height / 2;

	_looseRect = RECT();

	_looseRect.left = centerX - newW/2;
	_looseRect.right = _looseRect.left + newW;
	_looseRect.top = centerY - newH/2;
	_looseRect.bottom = _looseRect.top + newH;

	
	_isDivided = false;

	_maxHeight = 5;

	_deletedObjectList = std::list<shared_ptr<MObject>>();

	
}

void QuadNode::AddObject(shared_ptr<MObject> object, int Height)
{
	RECT rect = object->getRect();
	int pos = this->CheckRect(rect);

	float nodeWidth = this->getLooseRect().right - this->getLooseRect().left;
	float nodeHeight = this->getLooseRect().bottom - this->getLooseRect().top;
	float tWidth = rect.right - rect.left;
	float tHeight = rect.bottom - rect.top;

	//object belongs to current node
	if (pos == 0 || tWidth >= 0.25f*nodeWidth || tHeight >= 0.25f*nodeHeight || Height >= _maxHeight)
	{
		this->_objectList.insert(_objectList.end(),object);
		return;
	}
	//subdivide
	else
	{
		//this is a leaf node
		if (!_isDivided)
		{
			//_nodeList = (QuadNode**)malloc(4*sizeof(QuadNode*));
			_nodeList = new QuadNode*[4];

			if (!_nodeList)
			{
				MessageBox(NULL,"alloc failed","error!",MB_OK);
				return;
			}
			float midX = (_nodeRect.right + _nodeRect.left)/2;//_x + _width/2;
			float midY = (_nodeRect.top + _nodeRect.bottom)/2;//_y + _height/2;
			int halfw = (_nodeRect.right - _nodeRect.left)/2;//_width/2;
			int halfh = (_nodeRect.bottom - _nodeRect.top)/2;//_height/2;
			_nodeList[TL-1] = new QuadNode(_nodeRect.left,_nodeRect.top,halfw,halfh);
			_nodeList[TR-1] = new QuadNode(midX,_nodeRect.top,halfw,halfh);
			_nodeList[BR-1] = new QuadNode(midX,midY,halfw,halfh);
			_nodeList[BL-1] = new QuadNode(_nodeRect.left,midY,halfw,halfh);

			_isDivided = true;
		}

		//add object to approtiate child node
		//if (_nodeList[pos-1])
			_nodeList[pos-1]->AddObject(object,Height+1);
	}
}

//void QuadNode::removeObject(shared_ptr<MObject> object)
//{
//	this->_objectList.erase(object);
//}

void QuadNode::free()
{
	if (this->_isDivided)
	{
		for (int i=0;i<4;i++)
			if (this->_nodeList[i])
			{
				this->_nodeList[i]->free();
				delete this->_nodeList[i];
			}
		delete[] _nodeList;
	}
	//_objectList.clear();
}

std::list<shared_ptr<MObject>> QuadNode::getObjectList()
{
	return this->_objectList;
}

std::list<shared_ptr<MObject>> QuadNode::getMovingObjectList(const RECT &rect, bool remove)
{
	std::list<shared_ptr<MObject>> result = std::list<shared_ptr<MObject>>();
	std::list<shared_ptr<MObject>>::iterator it= _objectList.begin();
	while (it!= _objectList.end())
	{

		if (isIntersect((*it)->getRect(),rect) && (*it)->isMovable())
		{
			result.insert(result.end(),(*it));
			if (remove)
				_objectList.erase(it++);
		}
		else
		{
			if 	((*it)->getStatus() == -100)
			{
				//_deletedObjectList.insert(*it);
				_objectList.erase(it++);
			}
			else
				it++;
		}
	}
	return result;
}

std::list<shared_ptr<MObject>> QuadNode::getAllObjectList()
{
	std::list<shared_ptr<MObject>> contentList = this->getObjectList();
	if (!_isDivided)
		return contentList;
	else
	{
		std::list<shared_ptr<MObject>> objList = std::list<shared_ptr<MObject>>();
		std::list<shared_ptr<MObject>> tList;
		for (int i=0;i<4;i++)
		{
			tList = _nodeList[i]->getAllObjectList();
			objList.insert(objList.end(),tList.begin(),tList.end());
			objList.insert(objList.end(),contentList.begin(),contentList.end());
		}
		return objList;
	}
}

bool QuadNode::isDivided()
{
	return _isDivided;
}

QuadNode** QuadNode::getNodeList()
{
	return this->_nodeList;
}

bool QuadNode::isBelong(shared_ptr<MObject> object)
{
	if (this->CheckRect(object->getRect()) == 0)
		return true;
	else return false;
}

void QuadNode::setObjectList(const std::list<shared_ptr<MObject>> &newList)
{
	_objectList.clear();
	_objectList.insert(_objectList.end(),newList.begin(),newList.end());
}

int QuadNode::countObject()
{
	int k = this->_objectList.size();
	if (this->isDivided())
		for (int i=0;i<4;i++)
			k += this->_nodeList[i]->countObject();
	return k;
}

QuadTree::QuadTree(void)
{
	_width = 0;
	_height = 0;
	this->_root = new QuadNode(0,0,_width,_height);
}

QuadTree::QuadTree(int width, int height)
{
	_width = width;
	_height = height;
	this->_root = new QuadNode(0,0,_width,_height);

}


QuadTree::~QuadTree(void)
{
	_root->free();
}

void QuadTree::add(shared_ptr<MObject> object)
{
	_root->AddObject(object,0); 
}

QuadNode* QuadNode::getNode(const RECT &rect)
{
	int index;
	for (int i=1;i<=4;i++)
	{
		//kiểm tra xem vùng rect có thuộc 1 trong 4 node con ko
		index = this->CheckRect(rect);
		//nếu đây là node cần tìm
		if (index == 0)
			return this;
		//đệ quy xuống node con
		else return this->_nodeList[index];
	}
}

std::list<shared_ptr<MObject>> QuadNode::getCollidableObject(const RECT &rect)		//lấy tất cả các obj trong các node có rect có phần trùng với tham số rect
{
	std::list<shared_ptr<MObject>> objList = std::list<shared_ptr<MObject>>();
	std::list<shared_ptr<MObject>> tList = std::list<shared_ptr<MObject>>();
	std::list<shared_ptr<MObject>> currentList = this->getObjectList();
	if (!_isDivided)
	{
		std::list<shared_ptr<MObject>> rlist = std::list<shared_ptr<MObject>>();
		for (std::list<shared_ptr<MObject>>::iterator it = currentList.begin(); it != currentList.end();it++)
			if (isIntersect(rect,(*it)->getRect()))
				rlist.insert(rlist.end(),(*it));
		return rlist;
	}
	for (int i=0;i<4;i++)
	{
		if (this->isIntersect(rect,this->_nodeList[i]->getLooseRect()))
		{
			tList = this->_nodeList[i]->getCollidableObject(rect);
			//objList.insert(objList.end(),tList.begin(),tList.end());
			objList.insert(objList.end(),tList.begin(),tList.end());
		}
	}

	std::list<shared_ptr<MObject>> rlist = std::list<shared_ptr<MObject>>();
	for (std::list<shared_ptr<MObject>>::iterator it = currentList.begin(); it != currentList.end();it++)
		if (isIntersect(rect,(*it)->getRect()))
			rlist.insert(rlist.end(),(*it));
	objList.insert(objList.end(),rlist.begin(),rlist.end());
	return objList;
}

std::list<shared_ptr<MObject>> QuadNode::getMovableObjects(const RECT &rect, bool remove)		//lấy tất cả các obj trong các node có rect có phần trùng với tham số rect
{
	std::list<shared_ptr<MObject>> objList = std::list<shared_ptr<MObject>>();
	std::list<shared_ptr<MObject>> tList = std::list<shared_ptr<MObject>>();
	std::list<shared_ptr<MObject>> currentList = this->getMovingObjectList(rect,remove);
	if (!_isDivided)
	{
		/*std::list<shared_ptr<MObject>> rlist = std::list<shared_ptr<MObject>>();
		for (std::list<shared_ptr<MObject>>::iterator it = currentList.begin(); it != currentList.end();it++)
			if (isIntersect(rect,(*it)->getRect()) && (*it)->isMovable())
				rlist.insert((*it));
		return rlist;*/
		return currentList;
	}
	for (int i=0;i<4;i++)
	{
		if (this->isIntersect(rect,this->_nodeList[i]->getLooseRect()))
		{
			tList = this->_nodeList[i]->getMovableObjects(rect,remove);
			for (std::list<shared_ptr<MObject>>::iterator it = tList.begin(); it != tList.end();it++)
			//if ((*it)->isMovable())
			objList.insert(objList.end(),(*it));
		}
	}

	
	objList.insert(objList.end(),currentList.begin(),currentList.end());
	return objList;
}


QuadNode::~QuadNode(void)
{
	_objectList.clear();
}

bool QuadNode::isIntersect(RECT rect1, RECT rect2)
{
	if (rect1.top > rect2.bottom || rect1.bottom < rect2.top || rect1.left > rect2.right || rect1.right < rect2.left)
		return false;
	else return true;
}

RECT QuadNode::calChildRect(int ChildIndex)
{
	RECT rect = RECT();
	float width = _nodeRect.right - _nodeRect.left;
	float height = _nodeRect.bottom - _nodeRect.top;

	float tW = width/2;
	float tH = height/2;

	float newW = tW * offset;
	float newH = tH * offset;

	float centerX, centerY;

	
	switch (ChildIndex){
	case TL:
		{
			centerX = _nodeRect.left + tW/2;
			centerY = _nodeRect.top + tH/2;
			break;
		}
	case TR:
		{
			centerX = _nodeRect.left + tW + tW/2;
			centerY = _nodeRect.top + tH/2;
			break;
		}
	case BR:
		{
			centerX = _nodeRect.left + tW + tW/2;
			centerY = _nodeRect.top + tH + tH/2;
			break;
		}
	case BL:
		{
			centerX = _nodeRect.left + tW/2;
			centerY = _nodeRect.top + tH + tH/2;
			break;
		}
	}
	rect.left = centerX - newW/2;
	rect.top = centerY - newH/2;
	rect.right = rect.left + newW;
	rect.bottom = rect.top + newH;
	return rect;
}